#include <iostream>
#include <queue>
#include "binarytree.hpp"

using namespace std;

//构建二叉树
 void BinaryTree::BuildBinaryTree(const vector<int> &source)
 {
    if (source.empty())
        return;
    queue<TreeNode*> que;
    TreeNode* node = new TreeNode(source[0]);
    _root = node;
    que.push(node);
    for(size_t i = 1; i < source.size();)
    {
        TreeNode* cur = que.front();
        que.pop();
        cur->left = new TreeNode(source[i++]);
        que.push(cur->left);
        if (i < source.size())
        {
            cur->right = new TreeNode(source[i++]);
            que.push(cur->right);
        }
    }
 }

//二叉树总结点个数
    int BinaryTree::BinaryTreeNodeNum(TreeNode* root)
    {
        if (!root)
            return 0;
        return BinaryTreeNodeNum(root->left) + \
        BinaryTreeNodeNum(root->right) + \
        1;
    }


    //二叉树高度 
    int BinaryTree::BinaryTreeSize(TreeNode* root)
    { 
        if (!root)
            return 0;
        int left = BinaryTreeSize(root->left);
        int right = BinaryTreeSize(root->right);
        return left > right ? left + 1 : right + 1 ;
    }

    // 二叉树叶子节点个数
    int BinaryTree::BinaryTreeLeafSize(TreeNode* root)
    {
      return BinaryTreeLevelKSize(root, BinaryTreeSize(root));

    }

    // 二叉树第k层节点个数
    int BinaryTree::BinaryTreeLevelKSize(TreeNode* root, int k)
    {
        if (!root)
            return 0;
        if (k == 1)
            return 1;
        return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right,  k- 1);
    }

    // 二叉树查找值为x的节点
    TreeNode* BinaryTree::BinaryTreeFind(TreeNode* root, int x)
    {   
        //方案1
        //  if (!root)
        //     return nullptr;
        // queue<TreeNode*> que;
        // que.push(root);
        // while (!que.empty())
        // {
        //     TreeNode *cur = que.front();
        //     que.pop();
        //     if (cur->_val == x)
        //         return cur;
        //     if (cur->left)
        //         que.push(cur->left);
        //     if (cur->right)
        //         que.push(cur->right);

        // }
        // return nullptr;

        //方案2

        if (!root)
            return nullptr;
        if (root->_val == x)
            return root;
        TreeNode* left = BinaryTreeFind(root->left, x);
        if (left)
            return left;
        TreeNode* right = BinaryTreeFind(root->right, x);
        if (right)
            return right;
        
        return nullptr;
        

    }

    // 二叉树前序遍历
    void BinaryTree::BinaryTreePrevOrder(TreeNode* root)
    {
        if (!root)
            return;
        cout << root->_val << " ";
        BinaryTreePrevOrder(root->left);
        BinaryTreePrevOrder(root->right);
    }

    // 二叉树中序遍历
    void BinaryTree::BinaryTreeInOrder(TreeNode* root)
    {
        if (!root)
            return;
        BinaryTreeInOrder(root->left);
        cout << root->_val << " ";
        BinaryTreeInOrder(root->right);
    }

    // 二叉树后序遍历
    void BinaryTree::BinaryTreePostOrder(TreeNode* root)
    {
        if (!root)
            return;
        BinaryTreePostOrder(root->left);
        BinaryTreePostOrder(root->right);
        cout << root->_val << " ";
    }

    // 层序遍历
    void BinaryTree::BinaryTreeLevelOrder(TreeNode* root)
    {
        if (!root)
            return;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty())
        {
            TreeNode *cur = que.front();
            que.pop();
            cout << cur->_val << " ";
            if (cur->left)
                que.push(cur->left);
            if (cur->right)
                que.push(cur->right);

        }
        cout << endl;
    }
